#ifndef SOR_QSORT_H
#define SOR_QSORT_H

#include <iostream>
#include <cstring>
#include <cassert>

#include "core.h"

namespace JanSordid
{
	using namespace std;

	template <typename ITER>
	class QSort
	{
	private:
		const ITER _start;
		const ITER _end;

	public:
		// CTORs
		inline QSort( const ITER start, const ITER end )
			: _start( start ), _end( end )
		{
			assert( _start	!=	nullptr );
			assert( _end	!=	nullptr );
		}

		ITER partition( const ITER start, const ITER end )
		{
			assert( start	<	end );
			assert( start	!=	nullptr );
			assert( end		!=	nullptr );

			const ITER first = start+1;
			const ITER last = end-1;
			{
				const ITER mid = start + ((end - start) / 2);
				const ITER pivot = MEDP( start, mid, last );
				//cout << *start << " " << *mid << " " << *last << endl;

				if( pivot != start )
				{
					SWAP( *pivot, *start );
				}
			}

			// Pivot at start now
			ITER
				i = first,
				j = last,
				pi = first,
				pj = last;

			const auto pivot_val = *start;
			cout << "pivot: " << pivot_val << endl;

			do
			{
				while( *i <= pivot_val )
				{
					if( *i == pivot_val )
					{
						SWAP( *i, *pi );
						pi++;
					}
					i++;
				}

				while( *j >= pivot_val )
				{
					if( *j == pivot_val )
					{
						SWAP( *j, *pj );
						pj--;
					}
					j--;
				}

				if( i < j )
					SWAP( *i, *j );
			}
			while( i < j );

			SWAP( *start, *j );
			j--;

			n_times_i( end-start, i )
				cout << *(start+i) << " ";
			cout << endl;

			cout
				<< first-start << " "
				<< pi-start << " "
				<< pj-start << " "
				<< last-start << " "
				<< endl;

			while( pi != first )
			{
				cout << "moving forward swaping " << pi-start << " with " << j-start << endl;
				SWAP( *pi, *j );
				pi--;
				j--;
			}

			while( pj != last )
			{
				cout << "moving backward swaping " << pj-start << " with " << i-start << endl;
				SWAP( *pj, *i );
				pj++;
				i++;
			}

			cout << *start << endl;

			cout << "part" << endl;
			return 0;
		}

		void sort( const ITER start, const ITER end )
		{
			cout << "sort" << endl;
//			while( start < end )
			{
				auto pivot = partition( start, end );
//				sort( start, pivot );
//				sort( pivot, end );
			}
		}

		inline void operator()()
		{
			cout << "()" << endl;
			sort( _start, _end );
		}
	};
}

#endif
